One of conventional interleave address generation apparatuses and interleave address generation methods is described in the Unexamined Japanese Patent Publication No. HEI 7-212250.
In accordance with the trend of the present times toward the worldwide standardization of a third-generation communication system, standardization plans on interleave are being proposed and GF interleave is one of the interleave methods currently being studied.
This GF interleave is one of block interleaves that perform processing on a two-dimensional array with the number of rows N=2r and the number of columns M=2c. The GF interleave sequentially rearranges bits (hereinafter referred to as “column exchanged”) of a bit string of M bits in length delimited row by row from the first row to Nth row in different sequences, and generates an interleave address pattern by reading the matrix subjected to the row exchange carried out according to the sequence based on a bit inversion method from the first row of the first column from top to bottom to the Nth row of the Mth column.
In the block-size matrix two-dimensional array above, an example of generating an interleave address pattern by calculating a row conversion pattern πi(j) will be explained.
FIG. 1 is a block diagram showing a configuration of a column exchange apparatus used for a conventional GF interleave.
In FIG. 1, memory 11 outputs vector αi0 corresponding to row number i (0<i<N) input to exclusive logical sum calculator 13. Memory 12 outputs vector αj corresponding to column number j (0≦j<M) input to exclusive logical sum calculator 13. Exclusive logical sum calculator 13 calculates an exclusive logical sum of αi0 and αj and outputs calculation result β to memory 14.
Memory 14 outputs column conversion pattern πi(j) for the ith row based on calculation result β. πi(j) is calculated from following expression (1).                                           π            i                    ⁡                      (            j            )                          =                  {                                                                                          log                    α                                    ⁡                                      (                                                                  α                                                  i                          0                                                                    +                                              α                        j                                                              )                                                                                                                                          for                      ⁢                                                                                           ⁢                      j                                        =                    0                                    ,                  1                  ,                  …                  ⁢                                                                           ,                                      M                    -                    2                                                                                                                                            log                    α                                    ⁡                                      (                                          α                                              i                        0                                                              )                                                                                                                    for                    ⁢                                                                                   ⁢                    j                                    =                                      M                    -                    1                                                                                                          (        1        )            
Furthermore, conversions in memory 11, memory 12 and memory 14 are carried out using the conversion table shown in FIG. 2.
FIG. 2 shows a conversion table used for the GF interleave.
The conversion table in FIG. 2 is a table that shows correspondences between power in a Galois field power expression and a vector expression with the Galois field polynomial basis.
The vector expression consists of vectors output from memory 11 and memory 12 and vectors input to memory 14. Power Logαβ in a power expression is a value input to memory 11 or memory 12 and a value output from memory 14.
Here, the column conversion pattern on the ith row is obtained through the operation shown below. By calculating parameter i0 corresponding to row number i in memory 11, vector αi0 corresponding to parameter i0 is output. Exclusive logical sum calculator 13 calculates an exclusive logical sum of αi0 and αj output from memory 11 and memory 12 and memory 14 outputs logαβ corresponding to calculation result β.
By fixing address value i of memory 11 and incrementing address value j of memory 12 from 0, column conversion pattern πi(j) corresponding to the ith row is generated.
Then, an example of interleave address generation is shown below.
FIG. 3A, FIG. 3B, FIG. 3C and FIG. 3D illustrate the process of generation of interleave addresses.
An example of creating an interleave address pattern of size 30 on an 8×4 two-dimensional array will be explained below.
First, the interleave address generation apparatus stores an interleave address pattern with addresses 0 to 7 rearranged in the column direction in memory (i=0, j=0 to 7).
Likewise, the interleave address generation apparatus stores an interleave address pattern with addresses 0 to 7 rearranged in different sequences from the next rows onward in memory (i=1 to 3, J=0 to 7). The storage result is shown in FIG. 3A.
Then, the interleave address generation apparatus performs rearrangement processing in row units. More specifically, row i=1 and row i=2 are switched round. The switching result is shown in FIG. 3B.
Then, the interleave address generation apparatus adds an offset address to the stored value in row units. More specifically, a value obtained by multiplying the value of i by the number of column components is added to the value of i. For example, value 16 obtained by multiplying 2, the value of i, by 8, the number of components, is added to values on the 2nd column respectively. Value 8 obtained by multiplying 1, the value of i, by 8, the number of components, is added to values on the 3rd column respectively. Value 24 obtained by multiplying 3, the value of 1, by 8, the number of components, is added to values on the 4th column respectively. The addition result is shown in FIG. 3C.
Then, the interleave address generation apparatus extracts addresses in the column direction from memory and outputs only addresses smaller than the size of the interleave address pattern to be created. More specifically, in FIG. 3C, value 7 stored in i=0, j=0 is output and then value 20 stored in i=2, j=0, value 14 stored in i=1, j=0 and value 29 stored in i=3, j=0 are output. Then, value 3 stored in i=0, j=1 is output and then value 22 stored in i=2, j=1, value 12 stored in i=1, j=1 and value 26 stored in i=3, j=1 are output. Likewise, the interleave address generation apparatus extracts values stored in memory in the column direction and outputs the extracted values as an interleave address pattern. FIG. 3D shows the interleave address pattern output.
However, the conventional interleave address generation method develops an interleave address pattern created in predetermined units in memory and then performs row rearrangement and an addition of offset addresses, and thus the conventional interleave address generation method has a problem that a considerable memory space and considerable processing time are required to generate an interleave address pattern.